package interviewQuestions;

import java.util.Arrays;

/**
 * 输出走完所有的格子的路径
 * 输出 从 布满n*m个格子中的任意一个位置出发，走完所有格子的路径
 *
 * */
public class WalkAllMatrix {
    /**
     * @param matrix 格子的数组
     * @param counter 代表访问了多少个格子
     * @param x 在格子数组中的行位置
     * @param y 在格子数组中的列位置
     *
     * */
    public static boolean walkAllMatrix(int x,int y,int[][] matrix, int counter,int[] ans){
        /**
         * 终止条件
         * 当counter等于格子的总数时说明已经全部走完了
         * 当 周围是边界 或者是 已经访问过的结点时
         * */
        if (counter == matrix.length*matrix[0].length){
            return true;
        }
        if(x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length){
            return false;
        }
        if(matrix[x][y] == 1){
            return false;
        }

        matrix[x][y] = 1;
        ans[counter] = x*matrix[0].length + y +1;

        if(walkAllMatrix(x+1,y,matrix,counter+1,ans))
            return true;
        if(walkAllMatrix(x,y+1,matrix,counter+1,ans))
            return true;
        if(walkAllMatrix(x-1,y,matrix,counter+1,ans)){
            return true;
        }
        if(walkAllMatrix(x,y-1,matrix,counter+1,ans)){
            return true;
        }

        return false;

    }

    public static void main(String[] args) {
        int[][] matrix = new int[3][4];
        int[] ans = new int[12];
        walkAllMatrix(2,1,matrix,0,ans);
        for (int i : ans){
            System.out.println(i);
        }

    }

}
